|
A tree ''k''-spanner (or simply ''k''-spanner) of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most k times their distance in G. ==Known Results== There are several papers written on the subject of tree spanners. One of these was entitled ''Tree Spanners''〔http://epubs.siam.org/doi/abs/10.1137/S0895480192237403〕 written by mathematicians Leizhen Cai and Derek Corneil, which explored theoretical and algorithmic problems associated with tree spanners. Some of the conclusions from that paper are listed below: (1) A tree 1-spanner, if it exists, is a minimum spanning tree and can be found in O(m log β (m,n))time (in terms of complexity) for a weighted graph, where β (m,n) = min. (2) A tree 2-spanner can be constructed in linear time, and the tree t-spanner problem is NP-complete for any fixed integer . (3)The complexity for finding a minimum tree spanner in a digraph is O((m+n)α(m+n,n)) , where α(m+n,n) is a functional inverse of the Ackermann function, m is the number of vertices of the graph, and n is its number of edges. (4) The minimum 1-spanner of a weighted graph can be found in time. (5) For any fixed rational number , it is NP-complete to determine whether a weighted graph contains a tree t-spanner, even if all edge weights are positive integers. (6) A tree spanner (or a minimum tree spanner) of a digraph can be found in linear time. (7) A digraph contains at most one tree spanner. (8) The quasi-tree spanner of a weighted digraph can be found in O(m \times log β(m,n)) time. (9) The tree 1-spanner of a weighted graph G is a minimum spanning tree. Furthermore, every tree 1-spanner admissible weighted graph contains a unique minimum spanning tree. (10) A tree 2-spanner (if it exists) of a graph can be found in time. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tree spanner」の詳細全文を読む スポンサード リンク
|